package leetcode;

import java.util.HashMap;
import java.util.Map;

public class LC49 {
    int max = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        maxSum(root);
        return max;
    }
    public int maxSum(TreeNode root) {
        if (root == null) return 0;
        int left = Math.max(maxSum(root.left),0);
        int right = Math.max(maxSum(root.right),0);
        int x = Math.max(left, right) + root.val;
        max = Math.max(max,root.val+left+right);
        return x;
    }

}
